//
// Created by francklinson on 2021/10/21 AT 14:36.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int countQuadruplets(vector<int> &nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    for (int l = k + 1; l < n; ++l) {
                        if (nums[i] + nums[j] + nums[k] == nums[l])
                            ++ans;
                    }
                }
            }
        }
        return ans;
    }

    int countQuadruplets2(vector<int> &nums) {
        // 以第二个数为基点
        // 找左边的和、右边的差
        int n = nums.size();
        unordered_map<int, int> um;
        int ans = 0;
        for (int i = 1; i < n - 2; ++i) {
            for (int j = 0; j < i; ++j) {
                um[nums[i] + nums[j]]++;
            }
            for (int j = i + 2; j < n; ++j) {
                // 注意这里进行比较的元素  是i+1后面的和i+1进行比较
                // 因为i+2及以后元素进行的比较会在下一个i进行
                // 很精妙
                if (um.count(nums[j] - nums[i + 1])) {
                    ans += um[nums[j] - nums[i + 1]];
                }
            }
        }
        return ans;
    }

};

int main() {
    vector<int> nums{1, 1, 1, 3, 5};
    Solution solution;
    cout << solution.countQuadruplets2(nums) << endl;
    return 0;
}

